# 使用动态规划算法解决找零问题

def dpMakeChange(coinValueList, change, minCoins):
    # 从1分开始到change逐个计算最少硬币数
    for cents in range(1, change+1):
        # 初始化一个最大值
        coinCount = cents
        temp = [c for c in coinValueList if c <= cents]
        # 减去每个硬币面值, 向后查最少硬币数, 同时记录总的最少数
        for j in temp:
            if minCoins[cents-j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
        # 得到当前最少硬币数, 记录到表中
        minCoins[cents] = coinCount
    return minCoins[change]

# print(dpMakeChange([1,5,10,25], 6, [0]*7))

# 带有找零所需硬币的动态规划


def dpMakeChangeUsed(coinValueList, change, minCoins, coinsUsed):
    for cents in range(1, change+1):
        coinCount = cents
        newCoin = 1
        temp = [c for c in coinValueList if c <= cents]
        for j in temp:
            if minCoins[cents-j]+1 < coinCount:
                coinCount = minCoins[cents-j] + 1
                newCoin = j
        minCoins[cents] = coinCount
        coinsUsed[cents] = newCoin
    return minCoins[change]


def printCoins(coinsUsed, change):
    coin = change
    while coin > 0:
        thisCoin = coinsUsed[coin]
        print(thisCoin)
        coin -= thisCoin

# if __name__ == '__main__':
#     amnt = 63
#     clist = [1,5, 10, 25]
#     coinUsed = [0]*(amnt+1)
#     coinCount = [0]*(amnt+1)

#     print("Making change for ", amnt, "requires")
#     print(dpMakeChangeUsed(clist, amnt, coinCount, coinUsed), 'coins')
#     print("They are:")
#     printCoins(coinUsed, amnt)
#     print("The used list is as follows:")
#     print(coinUsed)


# 动态规划算法解决博物馆大盗问题
# 宝物的重量和价值
tr = [None,
      {'w': 2, 'v': 3},
      {'w': 3, 'v': 4},
      {'w': 4, 'v': 8},
      {'w': 5, 'v': 8},
      {'w': 9, 'v': 10}]
# 强盗最大负重
max_w = 20

# 初始化二位表格
# 以元组(i, w)作为字典的key, 将其所有宝物的组合价值都置为0
m = {(i, w): 0 for i in range(len(tr)) for w in range(max_w+1)}

# 填写二维表格
for i in range(1, len(tr)):
    for w in range(1, max_w+1):
        if tr[i]['w'] > w:
            m[(i, w)] = m[(i-1, w)]
        else:
            m[(i, w)] = max(m[(i-1, w)], m[(i-1, w-tr[i]['w'])]+tr[i]['v'])
print(m)
print(m[(len(tr)-1), max_w])
